SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>QR algorithm</title>

</head>

QR algorithm

</h1>

</header>

In <a href="Numerical_linear_algebra" title="Numerical linear algebra">numerical linear algebra</a>, the QR algorithm or QR iteration is an <a href="Eigenvalue_algorithm" title="Eigenvalue algorithm">eigenvalue algorithm</a>: that is, a procedure to calculate the <a href="Eigenvalues_and_eigenvectors" title="Eigenvalues and eigenvectors">eigenvalues and eigenvectors</a> of a <a href="Matrix_(mathematics)" title="Matrix (mathematics)">matrix</a>. The QR algorithm was developed in the late 1950s by <a href="John_G._F._Francis" title="John G. F. Francis">John G. F. Francis</a> and by <a href="Vera_N._Kublanovskaya" class="mw-redirect" title="Vera N. Kublanovskaya">Vera N. Kublanovskaya</a>, working independently.<a href="#cite_note-1">[1]</a><a href="#cite_note-2">[2]</a><a href="#cite_note-3">[3]</a> The basic idea is to perform a <a href="QR_decomposition" title="QR decomposition">QR decomposition</a>, writing the matrix as a product of an <a href="Orthogonal_matrix" title="Orthogonal matrix">orthogonal matrix</a> and an upper <a href="Triangular_matrix" title="Triangular matrix">triangular matrix</a>, multiply the factors in the reverse order, and iterate.

<div class="mw-heading mw-heading2"><h2 id="The_practical_QR_algorithm">The practical QR algorithm</h2></div>

Formally, let A be a real matrix of which we want to compute the eigenvalues, and let A0 := A. At the k-th step (starting with k = 0), we compute the <a href="QR_decomposition" title="QR decomposition">QR decomposition</a> Ak = Qk Rk where Qk is an <a href="Orthogonal_matrix" title="Orthogonal matrix">orthogonal matrix</a> (i.e., QT = Q−1) and Rk is an upper triangular matrix. We then form Ak+1 = Rk Qk. Note that

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</msubsup>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</msubsup>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</msubsup>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A_{k+1}=R_{k}Q_{k}=Q_{k}^{-1}Q_{k}R_{k}Q_{k}=Q_{k}^{-1}A_{k}Q_{k}=Q_{k}^{\mathsf {T}}A_{k}Q_{k},}</annotation>

</semantics>

</math>

so all the Ak are <a href="Similar_matrix" class="mw-redirect" title="Similar matrix">similar</a> and hence they have the same eigenvalues. The algorithm is <a href="Numerical_stability" title="Numerical stability">numerically stable</a> because it proceeds by orthogonal similarity transforms.

Under certain conditions,<a href="#cite_note-golubvanloan-4">[4]</a> the matrices Ak converge to a triangular matrix, the <a href="Schur_form" class="mw-redirect" title="Schur form">Schur form</a> of A. The eigenvalues of a triangular matrix are listed on the diagonal, and the eigenvalue problem is solved. In testing for convergence it is impractical to require exact zeros, but the <a href="Gershgorin_circle_theorem" title="Gershgorin circle theorem">Gershgorin circle theorem</a> provides a bound on the error.

If the matrices converge, then the eigenvalues along the diagonal will appear according to their geometric multiplicity. To guarantee convergence, A must be a symmetric matrix, and for all non zero eigenvalues <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \lambda }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \lambda }</annotation>

</semantics>

</math><img src="./b43d0ea3c9c025af1be9128e62a18fa74bedda2a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.355ex; height:2.176ex;" alt="{\displaystyle \lambda }" loading="lazy"> there must not be a corresponding eigenvalue <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle -\lambda }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle -\lambda }</annotation>

</semantics>

</math><img src="./0b7273c3daae98ce0f6c46098ad78933c621c835.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:3.163ex; height:2.343ex;" alt="{\displaystyle -\lambda }" loading="lazy">.<a href="#cite_note-5">[5]</a> Due to the fact that a single QR iteration has a cost of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}(n^{3})}">

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(n^{3})}</annotation>

</semantics>

</math><img src="./ff78e74de3bf7a5246829c66bc5acf0c2a94b67c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.108ex; height:3.176ex;" alt="{\displaystyle {\mathcal {O}}(n^{3})}" loading="lazy"> and the convergence is linear, the standard QR algorithm is extremely expensive to compute, especially considering it is not guaranteed to converge.<a href="#cite_note-6">[6]</a>

<div class="mw-heading mw-heading3"><h3 id="Using_Hessenberg_form">Using Hessenberg form</h3></div>

In the above crude form the iterations are relatively expensive. This can be mitigated by first bringing the matrix A to upper <a href="Hessenberg_form" class="mw-redirect" title="Hessenberg form">Hessenberg form</a> (which costs <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle {\tfrac {10}{3}}n^{3}+{\mathcal {O}}(n^{2})}">

<mfrac>

</mfrac>

</mstyle>

</mrow>

<msup>

</mrow>

</msup>

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle {\tfrac {10}{3}}n^{3}+{\mathcal {O}}(n^{2})}</annotation>

</semantics>

</math><img src="./b92ce10b8ebebc0d9631e4ff178e294c52a88e2a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.338ex; width:13.878ex; height:3.676ex;" alt="{\textstyle {\tfrac {10}{3}}n^{3}+{\mathcal {O}}(n^{2})}" loading="lazy"> arithmetic operations using a technique based on <a href="Householder_transformation" title="Householder transformation">Householder reduction</a>), with a finite sequence of orthogonal similarity transforms, somewhat like a two-sided QR decomposition.<a href="#cite_note-Demmel-7">[7]</a><a href="#cite_note-Trefethen-8">[8]</a> (For QR decomposition, the Householder reflectors are multiplied only on the left, but for the Hessenberg case they are multiplied on both left and right.) Determining the QR decomposition of an upper Hessenberg matrix costs <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle 6n^{2}+{\mathcal {O}}(n)}">

<msup>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle 6n^{2}+{\mathcal {O}}(n)}</annotation>

</semantics>

</math><img src="./fc903137578157ec0f4288b1f61def95eab83a51.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.506ex; height:3.009ex;" alt="{\textstyle 6n^{2}+{\mathcal {O}}(n)}" loading="lazy"> arithmetic operations. Moreover, because the Hessenberg form is already nearly upper-triangular (it has just one nonzero entry below each diagonal), using it as a starting point reduces the number of steps required for convergence of the QR algorithm.

If the original matrix is <a href="Symmetric_matrix" title="Symmetric matrix">symmetric</a>, then the upper Hessenberg matrix is also symmetric and thus <a href="Tridiagonal_matrix" title="Tridiagonal matrix">tridiagonal</a>, and so are all the Ak. In this case reaching Hessenberg form costs <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle {\tfrac {4}{3}}n^{3}+{\mathcal {O}}(n^{2})}">

<mfrac>

</mfrac>

</mstyle>

</mrow>

<msup>

</mrow>

</msup>

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle {\tfrac {4}{3}}n^{3}+{\mathcal {O}}(n^{2})}</annotation>

</semantics>

</math><img src="./ccd058ed49e533a2bbf43d4054370973dd18a88b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.338ex; width:13.056ex; height:3.676ex;" alt="{\textstyle {\tfrac {4}{3}}n^{3}+{\mathcal {O}}(n^{2})}" loading="lazy"> arithmetic operations using a technique based on Householder reduction.<a href="#cite_note-Demmel-7">[7]</a><a href="#cite_note-Trefethen-8">[8]</a> Determining the QR decomposition of a symmetric tridiagonal matrix costs <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}(n)}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(n)}</annotation>

</semantics>

</math><img src="./3c7bbe0124ae81792773344bc8709fc2f9c9910d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.054ex; height:2.843ex;" alt="{\displaystyle {\mathcal {O}}(n)}" loading="lazy"> operations.<a href="#cite_note-9">[9]</a>

<div class="mw-heading mw-heading3"><h3 id="Iteration_phase">Iteration phase</h3></div>

If a Hessenberg matrix <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A}</annotation>

</semantics>

</math><img src="./7daff47fa58cdfd29dc333def748ff5fa4c923e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}" loading="lazy"> has element <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a_{k,k-1}=0}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a_{k,k-1}=0}</annotation>

</semantics>

</math><img src="./747624fbcef31e9d0e2f77b96a081ef9c40299e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:9.994ex; height:2.843ex;" alt="{\displaystyle a_{k,k-1}=0}" loading="lazy"> for some <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy">, i.e., if one of the elements just below the diagonal is in fact zero, then it decomposes into blocks whose eigenproblems may be solved separately; an eigenvalue is either an eigenvalue of the submatrix of the first <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k-1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k-1}</annotation>

</semantics>

</math><img src="./21363ebd7038c93aae93127e7d910fc1b2e2c745.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.214ex; height:2.343ex;" alt="{\displaystyle k-1}" loading="lazy"> rows and columns, or an eigenvalue of the submatrix of remaining rows and columns. The purpose of the QR iteration step is to shrink one of these <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a_{k,k-1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a_{k,k-1}}</annotation>

</semantics>

</math><img src="./1858eb0bb97f4ecf67fe6626ee91341f7ed343b3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:5.733ex; height:2.343ex;" alt="{\displaystyle a_{k,k-1}}" loading="lazy"> elements so that effectively a small block along the diagonal is split off from the bulk of the matrix. In the case of a real eigenvalue that is usually the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1\times 1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1\times 1}</annotation>

</semantics>

</math><img src="./2b4bf91a527dc01af9ef6ace81199becf1308e00.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.165ex; height:2.176ex;" alt="{\displaystyle 1\times 1}" loading="lazy"> block in the lower right corner (in which case element <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a_{nn}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a_{nn}}</annotation>

</semantics>

</math><img src="./251db83006e16a85c7883b2303e1282f7ac09f7e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.434ex; height:2.009ex;" alt="{\displaystyle a_{nn}}" loading="lazy"> holds that eigenvalue), whereas in the case of a pair of conjugate complex eigenvalues it is the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2\times 2}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2\times 2}</annotation>

</semantics>

</math><img src="./f8a0e3400ffb97d67c00267ed50cddfe824cbe80.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.165ex; height:2.176ex;" alt="{\displaystyle 2\times 2}" loading="lazy"> block in the lower right corner.

The <a href="Rate_of_convergence" title="Rate of convergence">rate of convergence</a> depends on the separation between eigenvalues, so a practical algorithm will use shifts, either explicit or implicit, to increase separation and accelerate convergence. A typical symmetric QR algorithm isolates each eigenvalue (then reduces the size of the matrix) with only one or two iterations, making it efficient as well as robust.

<div class="mw-heading mw-heading4"><h4 id="A_single_iteration_with_explicit_shift">A single iteration with explicit shift</h4></div>

The steps of a QR iteration with explicit shift on a real Hessenberg matrix <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A}</annotation>

</semantics>

</math><img src="./7daff47fa58cdfd29dc333def748ff5fa4c923e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}" loading="lazy"> are:

<ol><li>Pick a shift <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mu }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mu }</annotation>

</semantics>

</math><img src="./9fd47b2a39f7a7856952afec1f1db72c67af6161.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:1.402ex; height:2.176ex;" alt="{\displaystyle \mu }" loading="lazy"> and subtract it from all diagonal elements, producing the matrix <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A-\mu I}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A-\mu I}</annotation>

</semantics>

</math><img src="./9e469634c31e1edd3771ee559a144b046f0943ea.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.157ex; height:2.676ex;" alt="{\displaystyle A-\mu I}" loading="lazy">. A basic strategy is to use <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mu =a_{n,n}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mu =a_{n,n}}</annotation>

</semantics>

</math><img src="./a1f2767f2819c40d5c295fc4c9cb19b92541b054.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:8.392ex; height:2.343ex;" alt="{\displaystyle \mu =a_{n,n}}" loading="lazy">, but there are more refined strategies that would further accelerate convergence. The idea is that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mu }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mu }</annotation>

</semantics>

</math><img src="./9fd47b2a39f7a7856952afec1f1db72c67af6161.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:1.402ex; height:2.176ex;" alt="{\displaystyle \mu }" loading="lazy"> should be close to an eigenvalue, since making this shift will accelerate convergence to that eigenvalue.</li>

<li>Perform a sequence of <a href="Givens_rotation" title="Givens rotation">Givens rotations</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{1},G_{2},\dots ,G_{n-1}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{1},G_{2},\dots ,G_{n-1}}</annotation>

</semantics>

</math><img src="./31304e286131bf8be919e32ed18c24b6e09d32ac.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:17.12ex; height:2.509ex;" alt="{\displaystyle G_{1},G_{2},\dots ,G_{n-1}}" loading="lazy"> on <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A-\mu I}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A-\mu I}</annotation>

</semantics>

</math><img src="./9e469634c31e1edd3771ee559a144b046f0943ea.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.157ex; height:2.676ex;" alt="{\displaystyle A-\mu I}" loading="lazy">, where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{i}}</annotation>

</semantics>

</math><img src="./0dd9fe8d455762608cc4e0a946b452492790ee5f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.626ex; height:2.509ex;" alt="{\displaystyle G_{i}}" loading="lazy"> acts on rows <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

</math><img src="./add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i+1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i+1}</annotation>

</semantics>

</math><img src="./2fe1bfc8314922e4c3fdb4e8eceb20a00b4f011d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:4.805ex; height:2.343ex;" alt="{\displaystyle i+1}" loading="lazy">, and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{i}}</annotation>

</semantics>

</math><img src="./0dd9fe8d455762608cc4e0a946b452492790ee5f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.626ex; height:2.509ex;" alt="{\displaystyle G_{i}}" loading="lazy"> is chosen to zero out position <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (i+1,i)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (i+1,i)}</annotation>

</semantics>

</math><img src="./8b8914f25636e08bde64ec94179761a287fb9f48.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.451ex; height:2.843ex;" alt="{\displaystyle (i+1,i)}" loading="lazy"> of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{i-1}\dotsb G_{1}(A-\mu I)}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{i-1}\dotsb G_{1}(A-\mu I)}</annotation>

</semantics>

</math><img src="./07a91db721cc724b3c60160d1fa65cabbf323599.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:20.072ex; height:2.843ex;" alt="{\displaystyle G_{i-1}\dotsb G_{1}(A-\mu I)}" loading="lazy">. This produces the upper triangular matrix <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R=G_{n-1}\dotsb G_{1}(A-\mu I)}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle R=G_{n-1}\dotsb G_{1}(A-\mu I)}</annotation>

</semantics>

</math><img src="./257cebcc2546a62d7699bf90d22d290bf4aca77b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:25.353ex; height:2.843ex;" alt="{\displaystyle R=G_{n-1}\dotsb G_{1}(A-\mu I)}" loading="lazy">. The orthogonal factor <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Q}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Q}</annotation>

</semantics>

</math><img src="./8752c7023b4b3286800fe3238271bbca681219ed.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.838ex; height:2.509ex;" alt="{\displaystyle Q}" loading="lazy"> would be <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{1}^{\mathrm {T} }G_{2}^{\mathrm {T} }\dotsb G_{n-1}^{\mathrm {T} }}">

</mrow>

</mrow>

</msubsup>

</mrow>

</mrow>

</msubsup>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{1}^{\mathrm {T} }G_{2}^{\mathrm {T} }\dotsb G_{n-1}^{\mathrm {T} }}</annotation>

</semantics>

</math><img src="./edb782d683cff7d527664fdda1f1d8ab704cdbb7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:15.134ex; height:3.343ex;" alt="{\displaystyle G_{1}^{\mathrm {T} }G_{2}^{\mathrm {T} }\dotsb G_{n-1}^{\mathrm {T} }}" loading="lazy">, but it is neither necessary nor efficient to produce that explicitly.</li>

<li>Now multiply <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle R}</annotation>

</semantics>

</math><img src="./4b0bfb3769bf24d80e15374dc37b0441e2616e33.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle R}" loading="lazy"> by the Givens matrices <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{1}^{\mathrm {T} }}">

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{1}^{\mathrm {T} }}</annotation>

</semantics>

</math><img src="./5ec20023805c056f0d3c8a361eaa8c5b8322332c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:3.246ex; height:3.176ex;" alt="{\displaystyle G_{1}^{\mathrm {T} }}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{2}^{\mathrm {T} }}">

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{2}^{\mathrm {T} }}</annotation>

</semantics>

</math><img src="./76d38127365037a84beee3a2c556c6cfe982b81e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:3.246ex; height:3.176ex;" alt="{\displaystyle G_{2}^{\mathrm {T} }}" loading="lazy">, ..., <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{n-1}^{\mathrm {T} }}">

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{n-1}^{\mathrm {T} }}</annotation>

</semantics>

</math><img src="./2f02e8414977bdd27eb8f802798e78a6002e7eb7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:5.146ex; height:3.343ex;" alt="{\displaystyle G_{n-1}^{\mathrm {T} }}" loading="lazy"> on the right, where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{i}^{\mathrm {T} }}">

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{i}^{\mathrm {T} }}</annotation>

</semantics>

</math><img src="./2a89c8d36ffd1696a63a98d7f4b849e5305e9087.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:3.246ex; height:3.176ex;" alt="{\displaystyle G_{i}^{\mathrm {T} }}" loading="lazy"> instead acts on columns <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

</math><img src="./add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i+1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i+1}</annotation>

</semantics>

</math><img src="./2fe1bfc8314922e4c3fdb4e8eceb20a00b4f011d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:4.805ex; height:2.343ex;" alt="{\displaystyle i+1}" loading="lazy">. This produces the matrix <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle RQ=RG_{1}^{\mathrm {T} }G_{2}^{\mathrm {T} }\dotsb G_{n-1}^{\mathrm {T} }}">

</mrow>

</mrow>

</msubsup>

</mrow>

</mrow>

</msubsup>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle RQ=RG_{1}^{\mathrm {T} }G_{2}^{\mathrm {T} }\dotsb G_{n-1}^{\mathrm {T} }}</annotation>

</semantics>

</math><img src="./1c30f0b1e597db5c73ee6942081feff233aa6041.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:23.599ex; height:3.343ex;" alt="{\displaystyle RQ=RG_{1}^{\mathrm {T} }G_{2}^{\mathrm {T} }\dotsb G_{n-1}^{\mathrm {T} }}" loading="lazy">, which is again on Hessenberg form.</li>

<li>Finally undo the shift by adding <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mu }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mu }</annotation>

</semantics>

</math><img src="./9fd47b2a39f7a7856952afec1f1db72c67af6161.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:1.402ex; height:2.176ex;" alt="{\displaystyle \mu }" loading="lazy"> to all diagonal entries. The result is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A'=RQ+\mu I}">

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A'=RQ+\mu I}</annotation>

</semantics>

</math><img src="./ced48003d97ce1352bdab849bde4176400fe0cd4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.542ex; height:3.009ex;" alt="{\displaystyle A'=RQ+\mu I}" loading="lazy">. Since <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Q}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Q}</annotation>

</semantics>

</math><img src="./8752c7023b4b3286800fe3238271bbca681219ed.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.838ex; height:2.509ex;" alt="{\displaystyle Q}" loading="lazy"> commutes with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle I}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle I}</annotation>

</semantics>

</math><img src="./535ea7fc4134a31cbe2251d9d3511374bc41be9f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.172ex; height:2.176ex;" alt="{\displaystyle I}" loading="lazy">, we have that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A'=Q^{\mathrm {T} }(A-\mu I)Q+\mu I=Q^{\mathrm {T} }AQ}">

<msup>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A'=Q^{\mathrm {T} }(A-\mu I)Q+\mu I=Q^{\mathrm {T} }AQ}</annotation>

</semantics>

</math><img src="./b2d5bbf7567e466b6eb61cdab485812d803e029a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:34.939ex; height:3.176ex;" alt="{\displaystyle A'=Q^{\mathrm {T} }(A-\mu I)Q+\mu I=Q^{\mathrm {T} }AQ}" loading="lazy">.</li></ol>

The purpose of the shift is to change which Givens rotations are chosen.

In more detail, the structure of one of these <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{i}}</annotation>

</semantics>

</math><img src="./0dd9fe8d455762608cc4e0a946b452492790ee5f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.626ex; height:2.509ex;" alt="{\displaystyle G_{i}}" loading="lazy"> matrices are

<msub>

</mrow>

</msub>

<mrow>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{i}={\begin{bmatrix}I&0&0&0\\0&c&-s&0\\0&s&c&0\\0&0&0&I\end{bmatrix}}}</annotation>

</semantics>

</math>

where the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle I}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle I}</annotation>

</semantics>

</math><img src="./535ea7fc4134a31cbe2251d9d3511374bc41be9f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.172ex; height:2.176ex;" alt="{\displaystyle I}" loading="lazy"> in the upper left corner is an <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (n-1)\times (n-1)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (n-1)\times (n-1)}</annotation>

</semantics>

</math><img src="./db79e223b655326d530528bb7efbc40128589985.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:17.254ex; height:2.843ex;" alt="{\displaystyle (n-1)\times (n-1)}" loading="lazy"> identity matrix, and the two scalars <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c=\cos \theta }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c=\cos \theta }</annotation>

</semantics>

</math><img src="./6baa53af54b1d724a7245a024f7b79172005a757.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:8.694ex; height:2.176ex;" alt="{\displaystyle c=\cos \theta }" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s=\sin \theta }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s=\sin \theta }</annotation>

</semantics>

</math><img src="./2a780f95c74931076ff3a877ec63685ce848744e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:8.522ex; height:2.176ex;" alt="{\displaystyle s=\sin \theta }" loading="lazy"> are determined by what rotation angle <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \theta }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \theta }</annotation>

</semantics>

</math><img src="./6e5ab2664b422d53eb0c7df3b87e1360d75ad9af.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.09ex; height:2.176ex;" alt="{\displaystyle \theta }" loading="lazy"> is appropriate for zeroing out position <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (i+1,i)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (i+1,i)}</annotation>

</semantics>

</math><img src="./8b8914f25636e08bde64ec94179761a287fb9f48.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.451ex; height:2.843ex;" alt="{\displaystyle (i+1,i)}" loading="lazy">. It is not necessary to exhibit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \theta }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \theta }</annotation>

</semantics>

</math><img src="./6e5ab2664b422d53eb0c7df3b87e1360d75ad9af.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.09ex; height:2.176ex;" alt="{\displaystyle \theta }" loading="lazy">; the factors <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c}</annotation>

</semantics>

</math><img src="./86a67b81c2de995bd608d5b2df50cd8cd7d92455.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.007ex; height:1.676ex;" alt="{\displaystyle c}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s}</annotation>

</semantics>

</math><img src="./01d131dfd7673938b947072a13a9744fe997e632.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.09ex; height:1.676ex;" alt="{\displaystyle s}" loading="lazy"> can be determined directly from elements in the matrix <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{i}}</annotation>

</semantics>

</math><img src="./0dd9fe8d455762608cc4e0a946b452492790ee5f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.626ex; height:2.509ex;" alt="{\displaystyle G_{i}}" loading="lazy"> should act on. Nor is it necessary to produce the whole matrix; multiplication (from the left) by <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{i}}</annotation>

</semantics>

</math><img src="./0dd9fe8d455762608cc4e0a946b452492790ee5f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.626ex; height:2.509ex;" alt="{\displaystyle G_{i}}" loading="lazy"> only affects rows <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

</math><img src="./add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i+1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i+1}</annotation>

</semantics>

</math><img src="./2fe1bfc8314922e4c3fdb4e8eceb20a00b4f011d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:4.805ex; height:2.343ex;" alt="{\displaystyle i+1}" loading="lazy">, so it is easier to just update those two rows in place. Likewise, for the Step 3 multiplication by <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{i}^{\mathrm {T} }}">

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{i}^{\mathrm {T} }}</annotation>

</semantics>

</math><img src="./2a89c8d36ffd1696a63a98d7f4b849e5305e9087.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:3.246ex; height:3.176ex;" alt="{\displaystyle G_{i}^{\mathrm {T} }}" loading="lazy"> from the right, it is sufficient to remember <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

</math><img src="./add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c}</annotation>

</semantics>

</math><img src="./86a67b81c2de995bd608d5b2df50cd8cd7d92455.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.007ex; height:1.676ex;" alt="{\displaystyle c}" loading="lazy">, and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s}</annotation>

</semantics>

</math><img src="./01d131dfd7673938b947072a13a9744fe997e632.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.09ex; height:1.676ex;" alt="{\displaystyle s}" loading="lazy">.

If using the simple <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mu =a_{n,n}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mu =a_{n,n}}</annotation>

</semantics>

</math><img src="./a1f2767f2819c40d5c295fc4c9cb19b92541b054.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:8.392ex; height:2.343ex;" alt="{\displaystyle \mu =a_{n,n}}" loading="lazy"> strategy, then at the beginning of Step 2 we have a matrix

<msub>

</mrow>

</msub>

<mrow>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A-a_{n,n}I={\begin{pmatrix}\times &\times &\times &\times &\times \\\times &\times &\times &\times &\times \\0&\times &\times &\times &\times \\0&0&\times &\times &\times \\0&0&0&\times &0\end{pmatrix}}}</annotation>

</semantics>

</math>

where the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \times }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \times }</annotation>

</semantics>

</math><img src="./0ffafff1ad26cbe49045f19a67ce532116a32703.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: 0.019ex; margin-bottom: -0.19ex; width:1.808ex; height:1.509ex;" alt="{\displaystyle \times }" loading="lazy"> denotes “could be whatever”. The first Givens rotation <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{1}}</annotation>

</semantics>

</math><img src="./e6ea4f4668b8334c8a7d3d284b0fd22131ef5f52.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.881ex; height:2.509ex;" alt="{\displaystyle G_{1}}" loading="lazy"> zeroes out the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (i+1,i)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (i+1,i)}</annotation>

</semantics>

</math><img src="./8b8914f25636e08bde64ec94179761a287fb9f48.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.451ex; height:2.843ex;" alt="{\displaystyle (i+1,i)}" loading="lazy"> position of this, producing

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<mrow>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{1}(A-a_{n,n}I)={\begin{pmatrix}\times &\times &\times &\times &\times \\0&\times &\times &\times &\times \\0&\times &\times &\times &\times \\0&0&\times &\times &\times \\0&0&0&\times &0\end{pmatrix}}{\text{.}}}</annotation>

</semantics>

</math>

Each new rotation zeroes out another subdiagonal element, thus increasing the number of known zeroes until we are at

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<mrow>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle H=G_{n-2}\dotsb G_{1}(A-a_{n,n}I)={\begin{pmatrix}\times &\times &\times &\times &\times \\0&\times &\times &\times &\times \\0&0&\times &\times &\times \\0&0&0&h_{n-1,n-1}&h_{n-1,n}\\0&0&0&h_{n,n-1}&0\end{pmatrix}}{\text{.}}}</annotation>

</semantics>

</math>

The final rotation <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{n-1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{n-1}}</annotation>

</semantics>

</math><img src="./ed301f68203f292061eb7f09a112d7ba21ff53a8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.146ex; height:2.509ex;" alt="{\displaystyle G_{n-1}}" loading="lazy"> has <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (c,s)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (c,s)}</annotation>

</semantics>

</math><img src="./95154d1aa637f24e189aaa9f64b18c24da4b3c6e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.941ex; height:2.843ex;" alt="{\displaystyle (c,s)}" loading="lazy"> chosen so that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle sh_{n-1,n-1}+ch_{n,n-1}=0}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle sh_{n-1,n-1}+ch_{n,n-1}=0}</annotation>

</semantics>

</math><img src="./7da01c29974287428e7db85628f32053db6ebfbf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:23.502ex; height:2.843ex;" alt="{\displaystyle sh_{n-1,n-1}+ch_{n,n-1}=0}" loading="lazy">. If <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |h_{n-1,n-1}|\gg |h_{n,n-1}|}">

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |h_{n-1,n-1}|\gg |h_{n,n-1}|}</annotation>

</semantics>

</math><img src="./e0c3f087fb15c4672d8950c6e7f9a6b5cb224f7d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:20.505ex; height:3.009ex;" alt="{\displaystyle |h_{n-1,n-1}|\gg |h_{n,n-1}|}" loading="lazy">, as is typically the case when we approach convergence, then <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c\approx 1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c\approx 1}</annotation>

</semantics>

</math><img src="./86d1918df76949d9138da6da4217db9c75a21891.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.268ex; height:2.176ex;" alt="{\displaystyle c\approx 1}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |s|\ll 1}">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |s|\ll 1}</annotation>

</semantics>

</math><img src="./273e0b48203b1d2b53e707097d448152921058d2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.161ex; height:2.843ex;" alt="{\displaystyle |s|\ll 1}" loading="lazy">. Making this rotation produces

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<mrow>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

</mtable>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle R=G_{n-1}G_{n-2}\dotsb G_{1}(A-a_{n,n}I)={\begin{pmatrix}\times &\times &\times &\times &\times \\0&\times &\times &\times &\times \\0&0&\times &\times &\times \\0&0&0&\times &ch_{n-1,n}\\0&0&0&0&sh_{n-1,n}\end{pmatrix}}{\text{,}}}</annotation>

</semantics>

</math>

which is our upper triangular matrix. But now we reach Step 3, and need to start rotating data between columns. The first rotation acts on columns <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1}</annotation>

</semantics>

</math><img src="./92d98b82a3778f043108d4e20960a9193df57cbf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 1}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2}</annotation>

</semantics>

</math><img src="./901fc910c19990d0dbaaefe4726ceb1a4e217a0f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 2}" loading="lazy">, producing

</mrow>

</mrow>

</msubsup>

<mrow>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

</mtable>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle RG_{1}^{\mathrm {T} }={\begin{pmatrix}\times &\times &\times &\times &\times \\\times &\times &\times &\times &\times \\0&0&\times &\times &\times \\0&0&0&\times &ch_{n-1,n}\\0&0&0&0&sh_{n-1,n}\end{pmatrix}}{\text{.}}}</annotation>

</semantics>

</math>

The expected pattern is that each rotation moves some nonzero value from the diagonal out to the subdiagonal, returning the matrix to Hessenberg form. This ends at

</mrow>

</mrow>

</msubsup>

</mrow>

</mrow>

</msubsup>

<mrow>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

</mtable>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle RG_{1}^{\mathrm {T} }\dotsb G_{n-1}^{\mathrm {T} }={\begin{pmatrix}\times &\times &\times &\times &\times \\\times &\times &\times &\times &\times \\0&\times &\times &\times &\times \\0&0&\times &\times &\times \\0&0&0&-s^{2}h_{n-1,n}&csh_{n-1,n}\end{pmatrix}}{\text{.}}}</annotation>

</semantics>

</math>

Algebraically the form is unchanged, but numerically the element in position <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (n,n-1)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (n,n-1)}</annotation>

</semantics>

</math><img src="./0d59ce77261fe699812a84f1ee3ce0a8b58d4e65.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.636ex; height:2.843ex;" alt="{\displaystyle (n,n-1)}" loading="lazy"> has gotten a lot closer to zero: there used to be a factor <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s}</annotation>

</semantics>

</math><img src="./01d131dfd7673938b947072a13a9744fe997e632.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.09ex; height:1.676ex;" alt="{\displaystyle s}" loading="lazy"> gap between it and the diagonal element above, but now the gap is more like a factor <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s^{2}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s^{2}}</annotation>

</semantics>

</math><img src="./58d7841cee3671436949ee789b84a848fd150bd3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.145ex; height:2.676ex;" alt="{\displaystyle s^{2}}" loading="lazy">, and another iteration would make it factor <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s^{4}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s^{4}}</annotation>

</semantics>

</math><img src="./7680201b9310c5ca547fa725ce20cc31c95128bb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.145ex; height:2.676ex;" alt="{\displaystyle s^{4}}" loading="lazy">; we have quadratic convergence. Practically that means <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(1)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(1)}</annotation>

</semantics>

</math><img src="./e66384bc40452c5452f33563fe0e27e803b0cc21.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.745ex; height:2.843ex;" alt="{\displaystyle O(1)}" loading="lazy"> iterations per eigenvalue suffice for convergence, and thus overall we can complete in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n)}</annotation>

</semantics>

</math><img src="./34109fe397fdcff370079185bfdb65826cb5565a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.977ex; height:2.843ex;" alt="{\displaystyle O(n)}" loading="lazy"> QR steps, each of which does a mere <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n^{2})}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n^{2})}</annotation>

</semantics>

</math><img src="./6cd9594a16cb898b8f2a2dff9227a385ec183392.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.032ex; height:3.176ex;" alt="{\displaystyle O(n^{2})}" loading="lazy"> arithmetic operations (or as little as <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n)}</annotation>

</semantics>

</math><img src="./34109fe397fdcff370079185bfdb65826cb5565a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.977ex; height:2.843ex;" alt="{\displaystyle O(n)}" loading="lazy"> operations, in the case that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A}</annotation>

</semantics>

</math><img src="./7daff47fa58cdfd29dc333def748ff5fa4c923e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}" loading="lazy"> is symmetric).

<div class="mw-heading mw-heading2"><h2 id="Visualization">Visualization</h2></div>

The basic QR algorithm can be visualized in the case where A is a positive-definite symmetric matrix. In that case, A can be depicted as an <a href="Ellipse" title="Ellipse">ellipse</a> in 2 dimensions or an <a href="Ellipsoid" title="Ellipsoid">ellipsoid</a> in higher dimensions. The relationship between the input to the algorithm and a single iteration can then be depicted as in Figure 1 (click to see an animation). Note that the LR algorithm is depicted alongside the QR algorithm.

A single iteration causes the ellipse to tilt or "fall" towards the x-axis. In the event where the large <a href="Semi-major_and_semi-minor_axes" title="Semi-major and semi-minor axes">semi-axis</a> of the ellipse is parallel to the x-axis, one iteration of QR does nothing. Another situation where the algorithm "does nothing" is when the large semi-axis is parallel to the y-axis instead of the x-axis. In that event, the ellipse can be thought of as balancing precariously without being able to fall in either direction. In both situations, the matrix is diagonal. A situation where an iteration of the algorithm "does nothing" is called a <a href="Fixed_point_(mathematics)" title="Fixed point (mathematics)">fixed point</a>. The strategy employed by the algorithm is <a href="Fixed-point_iteration" title="Fixed-point iteration">iteration towards a fixed-point</a>. Observe that one fixed point is stable while the other is unstable. If the ellipse were tilted away from the unstable fixed point by a very small amount, one iteration of QR would cause the ellipse to tilt away from the fixed point instead of towards. Eventually though, the algorithm would converge to a different fixed point, but it would take a long time.

<div class="mw-heading mw-heading3"><h3 id="Finding_eigenvalues_versus_finding_eigenvectors">Finding eigenvalues versus finding eigenvectors</h3></div>

It's worth pointing out that finding even a single eigenvector of a symmetric matrix is not computable (in exact real arithmetic according to the definitions in <a href="Computable_analysis" title="Computable analysis">computable analysis</a>).<a href="#cite_note-10">[10]</a> This difficulty exists whenever the multiplicities of a matrix's eigenvalues are not knowable. On the other hand, the same problem does not exist for finding eigenvalues. The eigenvalues of a matrix are always computable.

We will now discuss how these difficulties manifest in the basic QR algorithm. This is illustrated in Figure 2. Recall that the ellipses represent positive-definite symmetric matrices. As the two eigenvalues of the input matrix approach each other, the input ellipse changes into a circle. A circle corresponds to a multiple of the identity matrix. A near-circle corresponds to a near-multiple of the identity matrix whose eigenvalues are nearly equal to the diagonal entries of the matrix. Therefore, the problem of approximately finding the eigenvalues is shown to be easy in that case. But notice what happens to the semi-axes of the ellipses. An iteration of QR (or LR) tilts the semi-axes less and less as the input ellipse gets closer to being a circle. The eigenvectors can only be known when the semi-axes are parallel to the x-axis and y-axis. The number of iterations needed to achieve near-parallelism increases without bound as the input ellipse becomes more circular.

While it may be impossible to compute the <a href="Eigendecomposition_of_a_matrix" title="Eigendecomposition of a matrix">eigendecomposition</a> of an arbitrary symmetric matrix, it is always possible to perturb the matrix by an arbitrarily small amount and compute the eigendecomposition of the resulting matrix. In the case when the matrix is depicted as a near-circle, the matrix can be replaced with one whose depiction is a perfect circle. In that case, the matrix is a multiple of the identity matrix, and its eigendecomposition is immediate. Be aware though that the resulting <a href="Eigenbasis" class="mw-redirect" title="Eigenbasis">eigenbasis</a> can be quite far from the original eigenbasis.

<div class="mw-heading mw-heading3"><h3 id="Speeding_up:_Shifting_and_deflation">Speeding up: Shifting and deflation</h3></div>

The slowdown when the ellipse gets more circular has a converse: It turns out that when the ellipse gets more stretched - and less circular - then the rotation of the ellipse becomes faster. Such a stretch can be induced when the matrix <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M}</annotation>

</semantics>

</math><img src="./f82cade9898ced02fdd08712e5f0c0151758a0dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.442ex; height:2.176ex;" alt="{\displaystyle M}" loading="lazy"> which the ellipse represents gets replaced with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M-\lambda I}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M-\lambda I}</annotation>

</semantics>

</math><img src="./91f217630eb0ff13a0e6bc43144b56406760a46d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:7.81ex; height:2.343ex;" alt="{\displaystyle M-\lambda I}" loading="lazy"> where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \lambda }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \lambda }</annotation>

</semantics>

</math><img src="./b43d0ea3c9c025af1be9128e62a18fa74bedda2a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.355ex; height:2.176ex;" alt="{\displaystyle \lambda }" loading="lazy"> is approximately the smallest eigenvalue of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M}</annotation>

</semantics>

</math><img src="./f82cade9898ced02fdd08712e5f0c0151758a0dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.442ex; height:2.176ex;" alt="{\displaystyle M}" loading="lazy">. In this case, the ratio of the two semi-axes of the ellipse approaches <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \infty }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \infty }</annotation>

</semantics>

</math><img src="./c26c105004f30c27aa7c2a9c601550a4183b1f21.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.324ex; height:1.676ex;" alt="{\displaystyle \infty }" loading="lazy">. In higher dimensions, shifting like this makes the length of the smallest semi-axis of an ellipsoid small relative to the other semi-axes, which speeds up convergence to the smallest eigenvalue, but does not speed up convergence to the other eigenvalues. This becomes useless when the smallest eigenvalue is fully determined, so the matrix must then be deflated, which simply means removing its last row and column.

The issue with the unstable fixed point also needs to be addressed. The shifting heuristic is often designed to deal with this problem as well: Practical shifts are often discontinuous and randomised. Wilkinson's shift—which is well-suited for symmetric matrices like the ones we're visualising—is in particular discontinuous.

<div class="mw-heading mw-heading2"><h2 id="The_implicit_QR_algorithm">The implicit QR algorithm</h2></div>

In modern computational practice, the QR algorithm is performed in an implicit version which makes the use of multiple shifts easier to introduce.<a href="#cite_note-golubvanloan-4">[4]</a> The matrix is first brought to upper Hessenberg form <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A_{0}=QAQ^{\mathsf {T}}}">

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A_{0}=QAQ^{\mathsf {T}}}</annotation>

</semantics>

</math><img src="./7face05cf3e6f28cc6841e470615432a99d74b87.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:12.667ex; height:3.009ex;" alt="{\displaystyle A_{0}=QAQ^{\mathsf {T}}}" loading="lazy"> as in the explicit version; then, at each step, the first column of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A_{k}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A_{k}}</annotation>

</semantics>

</math><img src="./72095229db907e86eb4343cb4736429fcc56507d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.832ex; height:2.509ex;" alt="{\displaystyle A_{k}}" loading="lazy"> is transformed via a small-size Householder similarity transformation to the first column of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p(A_{k})}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p(A_{k})}</annotation>

</semantics>

</math><img src="./37aef2ff28c90a89f5202d88cf96d6a580e64fa7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; margin-left: -0.089ex; width:5.9ex; height:2.843ex;" alt="{\displaystyle p(A_{k})}" loading="lazy"> (or <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p(A_{k})e_{1}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p(A_{k})e_{1}}</annotation>

</semantics>

</math><img src="./8b0fa832202096d98b468b751be0bbfffd407ce1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; margin-left: -0.089ex; width:8.038ex; height:2.843ex;" alt="{\displaystyle p(A_{k})e_{1}}" loading="lazy">), where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p(A_{k})}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p(A_{k})}</annotation>

</semantics>

</math><img src="./37aef2ff28c90a89f5202d88cf96d6a580e64fa7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; margin-left: -0.089ex; width:5.9ex; height:2.843ex;" alt="{\displaystyle p(A_{k})}" loading="lazy">, of degree <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r}</annotation>

</semantics>

</math><img src="./0d1ecb613aa2984f0576f70f86650b7c2a132538.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.049ex; height:1.676ex;" alt="{\displaystyle r}" loading="lazy">, is the polynomial that defines the shifting strategy (often <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p(x)=(x-\lambda )(x-{\bar {\lambda }})}">

<mover>

</mover>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p(x)=(x-\lambda )(x-{\bar {\lambda }})}</annotation>

</semantics>

</math><img src="./3769d71fce2a9de77eb502a4df7ef511927d5b06.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; margin-left: -0.089ex; width:22.165ex; height:3.009ex;" alt="{\displaystyle p(x)=(x-\lambda )(x-{\bar {\lambda }})}" loading="lazy">, where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \lambda }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \lambda }</annotation>

</semantics>

</math><img src="./b43d0ea3c9c025af1be9128e62a18fa74bedda2a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.355ex; height:2.176ex;" alt="{\displaystyle \lambda }" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\bar {\lambda }}}">

<mover>

</mover>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\bar {\lambda }}}</annotation>

</semantics>

</math><img src="./6b40caf100572a9cc91ebf6ff7079ca8dd9eeb59.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.355ex; height:2.509ex;" alt="{\displaystyle {\bar {\lambda }}}" loading="lazy"> are the two eigenvalues of the trailing <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2\times 2}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2\times 2}</annotation>

</semantics>

</math><img src="./f8a0e3400ffb97d67c00267ed50cddfe824cbe80.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.165ex; height:2.176ex;" alt="{\displaystyle 2\times 2}" loading="lazy"> principal submatrix of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A_{k}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A_{k}}</annotation>

</semantics>

</math><img src="./72095229db907e86eb4343cb4736429fcc56507d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.832ex; height:2.509ex;" alt="{\displaystyle A_{k}}" loading="lazy">, the so-called implicit double-shift). Then successive Householder transformations of size <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r+1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r+1}</annotation>

</semantics>

</math><img src="./7bf1b7e1e8ed2801660c299494ed10e6f18f790d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.052ex; height:2.343ex;" alt="{\displaystyle r+1}" loading="lazy"> are performed in order to return the working matrix <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A_{k}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A_{k}}</annotation>

</semantics>

</math><img src="./72095229db907e86eb4343cb4736429fcc56507d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.832ex; height:2.509ex;" alt="{\displaystyle A_{k}}" loading="lazy"> to upper Hessenberg form. This operation is known as bulge chasing, due to the peculiar shape of the non-zero entries of the matrix along the steps of the algorithm. As in the first version, deflation is performed as soon as one of the sub-diagonal entries of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A_{k}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A_{k}}</annotation>

</semantics>

</math><img src="./72095229db907e86eb4343cb4736429fcc56507d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.832ex; height:2.509ex;" alt="{\displaystyle A_{k}}" loading="lazy"> is sufficiently small.

<div class="mw-heading mw-heading3"><h3 id="Renaming_proposal">Renaming proposal</h3></div>

Since in the modern implicit version of the procedure no <a href="QR_decomposition" title="QR decomposition">QR decompositions</a> are explicitly performed, some authors, for instance Watkins,<a href="#cite_note-11">[11]</a> suggested changing its name to Francis algorithm. <a href="Gene_H._Golub" title="Gene H. Golub">Golub</a> and <a href="Charles_F._Van_Loan" title="Charles F. Van Loan">Van Loan</a> use the term Francis QR step.

<div class="mw-heading mw-heading2"><h2 id="Interpretation_and_convergence">Interpretation and convergence</h2></div>

The QR algorithm can be seen as a more sophisticated variation of the basic <a href="Power_iteration" title="Power iteration">"power" eigenvalue algorithm</a>. Recall that the power algorithm repeatedly multiplies A times a single vector, normalizing after each iteration. The vector converges to an eigenvector of the largest eigenvalue. Instead, the QR algorithm works with a complete basis of vectors, using QR decomposition to renormalize (and orthogonalize). For a symmetric matrix A, upon convergence, AQ = QΛ, where Λ is the <a href="Diagonal_matrix" title="Diagonal matrix">diagonal matrix</a> of eigenvalues to which A converged, and where Q is a composite of all the orthogonal similarity transforms required to get there. Thus the columns of Q are the eigenvectors.

<div class="mw-heading mw-heading2"><h2 id="History">History</h2></div>

The QR algorithm was preceded by the LR algorithm, which uses the <a href="LU_decomposition" title="LU decomposition">LU decomposition</a> instead of the QR decomposition. The QR algorithm is more stable, so the LR algorithm is rarely used nowadays. However, it represents an important step in the development of the QR algorithm.

The LR algorithm was developed in the early 1950s by <a href="Heinz_Rutishauser" title="Heinz Rutishauser">Heinz Rutishauser</a>, who worked at that time as a research assistant of <a href="Eduard_Stiefel" title="Eduard Stiefel">Eduard Stiefel</a> at <a href="ETH_Zurich" title="ETH Zurich">ETH Zurich</a>. Stiefel suggested that Rutishauser use the sequence of moments y0T Ak x0, k = 0, 1, ... (where x0 and y0 are arbitrary vectors) to find the eigenvalues of A. Rutishauser took an algorithm of <a href="Alexander_Aitken" title="Alexander Aitken">Alexander Aitken</a> for this task and developed it into the quotient–difference algorithm or qd algorithm. After arranging the computation in a suitable shape, he discovered that the qd algorithm is in fact the iteration Ak = LkUk (LU decomposition), Ak+1 = UkLk, applied on a tridiagonal matrix, from which the LR algorithm follows.<a href="#cite_note-12">[12]</a>

<div class="mw-heading mw-heading2"><h2 id="Other_variants">Other variants</h2></div>

One variant of the QR algorithm, the Golub-Kahan-Reinsch algorithm starts with reducing a general matrix into a bidiagonal one.<a href="#cite_note-13">[13]</a> This variant of the QR algorithm for the computation of <a href="Singular_values" class="mw-redirect" title="Singular values">singular values</a> was first described by <a href="#CITEREFGolubKahan1965">Golub & Kahan (1965)</a>. The <a href="LAPACK" title="LAPACK">LAPACK</a> subroutine <a rel="nofollow" class="external text" href="http://www.netlib.org/lapack/double/dbdsqr.f">DBDSQR</a> implements this <a href="Iterative_method" title="Iterative method">iterative method</a>, with some modifications to cover the case where the singular values are very small (<a href="#CITEREFDemmelKahan1990">Demmel & Kahan 1990</a>). Together with a first step using Householder reflections and, if appropriate, <a href="QR_decomposition" title="QR decomposition">QR decomposition</a>, this forms the <a rel="nofollow" class="external text" href="http://www.netlib.org/lapack/double/dgesvd.f">DGESVD</a> routine for the computation of the <a href="Singular_value_decomposition" title="Singular value decomposition">singular value decomposition</a>. The QR algorithm can also be implemented in infinite dimensions with corresponding convergence results.<a href="#cite_note-14">[14]</a><a href="#cite_note-15">[15]</a>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist reflist-columns references-column-width" style="column-width: 30em;">

<li id="cite_note-1"><a href="#cite_ref-1">^</a> J.G.F. Francis, "The QR Transformation, I", <a href="The_Computer_Journal" title="The Computer Journal">The Computer Journal</a>, 4(3), pages 265–271 (1961, received October 1959). <a href="https://doi.org/10.1093/comjnl/4.3.265" class="extiw external" title="doi:10.1093/comjnl/4.3.265">doi:10.1093/comjnl/4.3.265</a>

</li>

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFFrancis1962" class="citation journal cs1">Francis, J. G. F. (1962). <a rel="nofollow" class="external text" href="https://doi.org/10.1093%2Fcomjnl%2F4.4.332">"The QR Transformation, II"</a>. The Computer Journal. 4 (4): 332–345. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1093%2Fcomjnl%2F4.4.332">10.1093/comjnl/4.4.332</a>.</cite>

</li>

Vera N. Kublanovskaya, "On some algorithms for the solution of the complete eigenvalue problem," USSR Computational Mathematics and Mathematical Physics, vol. 1, no. 3, pages 637–657 (1963, received Feb 1961). Also published in: Zhurnal Vychislitel'noi Matematiki i Matematicheskoi Fiziki, vol.1, no. 4, pages 555–570 (1961). <a href="https://doi.org/10.1016/0041-5553(63)90168-X" class="extiw external" title="doi:10.1016/0041-5553(63)90168-X">doi:10.1016/0041-5553(63)90168-X</a>

</li>

<li id="cite_note-golubvanloan-4">^ <a href="#cite_ref-golubvanloan_4-0">a</a> <a href="#cite_ref-golubvanloan_4-1">b</a> <cite id="CITEREFGolubVan_Loan1996" class="citation book cs1">Golub, G. H.; Van Loan, C. F. (1996). Matrix Computations (3rd ed.). Baltimore: Johns Hopkins University Press. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-8018-5414-8</bdi>.</cite>

</li>

<li id="cite_note-5"><a href="#cite_ref-5">^</a> <cite id="CITEREFHolmes2023" class="citation book cs1">Holmes, Mark H. (2023). Introduction to scientific computing and data analysis. Texts in computational science and engineering (Second ed.). Cham: Springer. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-031-22429-4</bdi>.</cite>

</li>

<li id="cite_note-6"><a href="#cite_ref-6">^</a> <cite id="CITEREFGolubVan_Loan2013" class="citation book cs1">Golub, Gene H.; Van Loan, Charles F. (2013). Matrix computations. Johns Hopkins studies in the mathematical sciences (Fourth ed.). Baltimore: The Johns Hopkins University Press. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-4214-0794-4</bdi>.</cite>

</li>

<li id="cite_note-Demmel-7">^ <a href="#cite_ref-Demmel_7-0">a</a> <a href="#cite_ref-Demmel_7-1">b</a> <cite id="CITEREFDemmel1997" class="citation book cs1"><a href="James_W._Demmel" class="mw-redirect" title="James W. Demmel">Demmel, James W.</a> (1997). Applied Numerical Linear Algebra. SIAM.</cite>

</li>

<li id="cite_note-Trefethen-8">^ <a href="#cite_ref-Trefethen_8-0">a</a> <a href="#cite_ref-Trefethen_8-1">b</a> <cite id="CITEREFTrefethenBau1997" class="citation book cs1"><a href="Lloyd_N._Trefethen" class="mw-redirect" title="Lloyd N. Trefethen">Trefethen, Lloyd N.</a>; Bau, David (1997). Numerical Linear Algebra. SIAM.</cite>

</li>

<li id="cite_note-9"><a href="#cite_ref-9">^</a> <cite id="CITEREFOrtegaKaiser1963" class="citation journal cs1">Ortega, James M.; Kaiser, Henry F. (1963). <a rel="nofollow" class="external text" href="https://doi.org/10.1093%2Fcomjnl%2F6.1.99">"The LLT and QR methods for symmetric tridiagonal matrices"</a>. The Computer Journal. 6 (1): 99–101. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1093%2Fcomjnl%2F6.1.99">10.1093/comjnl/6.1.99</a>.</cite>

</li>

<li id="cite_note-10"><a href="#cite_ref-10">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://mathoverflow.net/questions/369930/why-is-uncomputability-of-the-spectral-decomposition-not-a-problem">"linear algebra - Why is uncomputability of the spectral decomposition not a problem?"</a>. MathOverflow. Retrieved 2021-08-09.</cite>

</li>

<li id="cite_note-11"><a href="#cite_ref-11">^</a> <cite id="CITEREFWatkins2007" class="citation book cs1">Watkins, David S. (2007). The Matrix Eigenvalue Problem: GR and Krylov Subspace Methods. Philadelphia, PA: SIAM. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-89871-641-2</bdi>.</cite>

</li>

<li id="cite_note-12"><a href="#cite_ref-12">^</a> <cite id="CITEREFParlettGutknecht2011" class="citation cs2">Parlett, Beresford N.; Gutknecht, Martin H. (2011), <a rel="nofollow" class="external text" href="http://doc.rero.ch/record/299139/files/drq003.pdf">"From qd to LR, or, how were the qd and LR algorithms discovered?"</a> (PDF), IMA Journal of Numerical Analysis, 31 (3): 741–754, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1093%2Fimanum%2Fdrq003">10.1093/imanum/drq003</a>, <a href="Hdl_(identifier)" class="mw-redirect" title="Hdl (identifier)">hdl</a>:<a rel="nofollow" class="external text" href="https://hdl.handle.net/20.500.11850%2F159536">20.500.11850/159536</a>, <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0272-4979">0272-4979</a></cite>

</li>

<li id="cite_note-13"><a href="#cite_ref-13">^</a> Bochkanov Sergey Anatolyevich. ALGLIB User Guide - General Matrix operations - Singular value decomposition . ALGLIB Project. 2010-12-11. URL:<a rel="nofollow" class="external autonumber" href="http://www.alglib.net/matrixops/general/svd.php">[1]</a>Accessed: 2010-12-11. (Archived by WebCite at

</li>

<li id="cite_note-14"><a href="#cite_ref-14">^</a> <cite id="CITEREFDeiftLiTomei1985" class="citation journal cs1">Deift, Percy; Li, Luenchau C.; Tomei, Carlos (1985). <a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0022-1236%2885%2990065-5">"Toda flows with infinitely many variables"</a>. Journal of Functional Analysis. 64 (3): 358–402. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0022-1236%2885%2990065-5">10.1016/0022-1236(85)90065-5</a>.</cite>

</li>

<li id="cite_note-15"><a href="#cite_ref-15">^</a> <cite id="CITEREFColbrookHansen2019" class="citation journal cs1">Colbrook, Matthew J.; Hansen, Anders C. (2019). <a rel="nofollow" class="external text" href="https://doi.org/10.1007%2Fs00211-019-01047-5">"On the infinite-dimensional QR algorithm"</a>. Numerische Mathematik. 143 (1): 17–83. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/2011.08172">2011.08172</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2Fs00211-019-01047-5">10.1007/s00211-019-01047-5</a>.</cite>

</li>

</ol></div>

<div class="mw-heading mw-heading2"><h2 id="Sources">Sources</h2></div>

<ul><li><cite id="CITEREFDemmelKahan1990" class="citation journal cs1"><a href="James_Demmel" title="James Demmel">Demmel, James</a>; <a href="William_Kahan" title="William Kahan">Kahan, William</a> (1990). "Accurate singular values of bidiagonal matrices". SIAM Journal on Scientific and Statistical Computing. 11 (5): 873–912. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.48.3740">10.1.1.48.3740</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2F0911052">10.1137/0911052</a>.</cite></li>

<li><cite id="CITEREFGolubKahan1965" class="citation journal cs1"><a href="Gene_H._Golub" title="Gene H. Golub">Golub, Gene H.</a>; <a href="William_Kahan" title="William Kahan">Kahan, William</a> (1965). "Calculating the singular values and pseudo-inverse of a matrix". Journal of the Society for Industrial and Applied Mathematics, Series B: Numerical Analysis. 2 (2): 205–224. <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/1965SJNA....2..205G">1965SJNA....2..205G</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2F0702016">10.1137/0702016</a>. <a href="JSTOR_(identifier)" class="mw-redirect" title="JSTOR (identifier)">JSTOR</a> <a rel="nofollow" class="external text" href="https://www.jstor.org/stable/2949777">2949777</a>.</cite></li></ul>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

<ul><li><a rel="nofollow" class="external text" href="https://planetmath.org/eigenvalueproblem">Eigenvalue problem</a> at <a href="PlanetMath" title="PlanetMath">PlanetMath</a>.</li>

<li><a rel="nofollow" class="external text" href="http://www-users.math.umn.edu/~olver/aims_/qr.pdf">Notes on orthogonal bases and the workings of the QR algorithm</a> by <a href="Peter_J._Olver" title="Peter J. Olver">Peter J. Olver</a></li>

<li><a rel="nofollow" class="external text" href="https://web.archive.org/web/20081209042103/http://math.fullerton.edu/mathews/n2003/QRMethodMod.html">Module for the QR Method</a></li>

<li><a rel="nofollow" class="external text" href="https://github.com/nom-de-guerre/Matrices">C++ Library</a></li></ul>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1236075235">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style></div><div role="navigation" class="navbox" aria-labelledby="Numerical_linear_algebra64" style="padding:3px"><table class="nowraplinks mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><style data-mw-deduplicate="TemplateStyles:r1239400231">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div id="Numerical_linear_algebra64" style="font-size:114%;margin:0 4em"><a href="Numerical_linear_algebra" title="Numerical linear algebra">Numerical linear algebra</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%">Key concepts</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Floating_point" class="mw-redirect" title="Floating point">Floating point</a></li>

<li><a href="Numerical_stability" title="Numerical stability">Numerical stability</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Problems</th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="System_of_linear_equations" title="System of linear equations">System of linear equations</a></li>

<li><a href="Matrix_decomposition" title="Matrix decomposition">Matrix decompositions</a></li>

<li><a href="Matrix_multiplication" title="Matrix multiplication">Matrix multiplication</a> (<a href="Matrix_multiplication_algorithm" title="Matrix multiplication algorithm">algorithms</a>)</li>

<li><a href="Matrix_splitting" title="Matrix splitting">Matrix splitting</a></li>

<li><a href="Sparse_matrix" title="Sparse matrix">Sparse problems</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Hardware</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="CPU_cache" title="CPU cache">CPU cache</a></li>

<li><a href="Cache-oblivious_algorithm" title="Cache-oblivious algorithm">Cache-oblivious algorithm</a></li>

<li><a href="Multiprocessing" title="Multiprocessing">Multiprocessing</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Software</th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Automatically_Tuned_Linear_Algebra_Software" title="Automatically Tuned Linear Algebra Software">ATLAS</a></li>

<li><a href="MATLAB" title="MATLAB">MATLAB</a></li>

<li><a href="Basic_Linear_Algebra_Subprograms" title="Basic Linear Algebra Subprograms">Basic Linear Algebra Subprograms (BLAS)</a></li>

<li><a href="LAPACK" title="LAPACK">LAPACK</a></li>

<li><a href="Comparison_of_linear_algebra_libraries" title="Comparison of linear algebra libraries">Specialized libraries</a></li>

<li><a href="Comparison_of_numerical-analysis_software" title="Comparison of numerical-analysis software">General purpose software</a></li></ul>

</div></td></tr></tbody></table></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-07-16" href="https://en.wikipedia.org/wiki/?title=QR_algorithm&oldid=1300875557">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>